#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
typedef long long ll;
using namespace std;



//class Solution {
//public:
//    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
//        int r = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
//        int l = r;
//        int n = arr.size();
//        vector<int> ans;
//        while (r - l + 1 < k) {
//            if (l == 0) {
//                r++;
//                continue;
//            }
//            if (r == n - 1) {
//                l--;
//                continue;
//            }
//            int ll = l - 1, rr = r + 1;
//            if (rr <= n - 1 && abs(arr[rr] - x) < abs(arr[ll] - x))
//                r = rr;
//            else
//                l = ll;
//        }
//        for (int i = l; i <= r && i - l + 1 <= k; i++) {
//            ans.push_back(arr[i]);
//        }
//        return ans;
//    }
//};

//class Solution {
//public:
//    int maxp = 0, maxn = 0, n;
//    vector<int>p;
//    vector<int>ans;
//    vector<int>time;
//    void TopVotedCandidate(vector<int>& persons, vector<int>& times) {
//        n = times.size();
//        p.resize(n);
//        ans.resize(n);
//        time.resize(n);
//        for (int i = 0; i < n; i++) {
//            time[i] = times[i];
//            p[persons[i]]++;
//            if (p[persons[i]] >= maxn) {
//                maxn = p[persons[i]];
//                maxp = persons[i];
//            }
//            ans[i] = maxp;
//        }
//    }
//
//    int q(int t) {
//        int pos =    - 1;
//        return ans[pos];
//    }
//};

//class TopVotedCandidate {
//public:
//    int maxp = 0, maxn = 0, n;
//    vector<int>p;
//    vector<int>ans;
//    vector<int>time;
//    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
//        n = times.size();
//        p.resize(n);
//        ans.resize(n);
//        time.resize(n);
//        for (int i = 0; i < n; i++) {
//            time[i] = times[i];
//            p[persons[i]]++;
//            if (p[persons[i]] >= maxn) {
//                maxn = p[persons[i]];
//                maxp = persons[i];
//            }
//            ans[i] = maxp;
//        }
//    }
//
//    int q(int t) {
//        int l = 0, r = n - 1, mid;
//        while (l < r) {
//            mid = (l + r + 1) >> 1;
//            if (t >= time[mid])
//                l = mid;
//            else
//                r = mid - 1;
//        }
//        return ans[r];
//    }
//};


//int main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//    Solution slove;
//    vector<int> test1 = { 0,1,1,0,0,1,0 };
//    vector<int> t = { 0,5,10,15,20,25,30 };
//    slove.TopVotedCandidate(test1, t);
//    while (1) {
//        int x = 1;
//        cin >> x;
//        cout << slove.q(x);
//    }
//
//
//
//    return 0;
//}


//int n,ans;
//int a[2000006];
//ll sum[2000006];
//deque <int>q;
//int main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cin >> n;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//		a[i + n] = a[i];
//		sum[i] = sum[i - 1] + a[i];
//	}
//	for (int i = n+1; i <= 2 * n - 1; i++)
//		sum[i] = sum[i - 1] + a[i];
//	
//	for (int i = 1; i <= 2 * n - 1;i++) {
//		while (!q.empty() && sum[q.back()] >= sum[i]) q.pop_back();
//		q.push_back(i);
//		if (i >= n  ) {
//			while (!q.empty() && q.front() <= i - n) q.pop_front();
//			if (sum[q.front()] - sum[i - n] >= 0) ans++;
//		}
//	}
//	cout << ans;
//	return 0;
//}